package Leetcode.树;

/**
 * @ClassName 前缀树
 * @since: 2023/9/7 14:13
 * @auth: kirito
 * @description:
 *
 * https://www.bilibili.com/video/BV1AP411p7pK/?spm_id_from=333.337.search-card.all.click&vd_source=bb13dc2c93abb249d3580e11536700c1
 **/
public class Trie  {
    private Trie[] children;  // 字典树的子节点数组
    private boolean isEnd;    // 标识当前节点是否为一个单词的结尾

    public Trie() {
        children = new Trie[26];  // 初始化子节点数组为26个字母
        isEnd = false;            // 初始时不是一个单词的结尾
    }

    //方法用于将单词插入到字典树中。它从根节点开始，逐个字符遍历单词，
    // 根据字符计算索引，如果子节点不存在则创建新的子节点，
    // 然后将指针移动到下一个子节点，最后在单词的最后一个字符节点上标记为单词的结尾。
    public void insert(String word) {
        Trie node = this;  // 从根节点开始插入
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';  // 计算当前字符在子节点数组中的索引
            if (node.children[index] == null) {
                node.children[index] = new Trie();  // 如果子节点不存在，创建新的子节点
            }
            node = node.children[index];  // 移动到下一个子节点
        }
        node.isEnd = true;  // 在单词的最后一个字符节点上标记为单词的结尾
    }

    //用于搜索完整的单词。它首先调用 searchPrefix() 方法搜索单词的前缀，
    // 如果找到前缀节点且该节点是一个单词的结尾，则返回 true，否则返回 false
    public boolean search(String word) {
        Trie node = searchPrefix(word);  // 先搜索前缀
        return node != null && node.isEnd;  // 如果找到前缀节点且是一个单词的结尾，返回true
    }

    //用于判断是否存在以给定前缀开始的单词。它调用 searchPrefix() 方法搜索前缀，
    // 如果找到前缀节点，则返回 true，否则返回 false。
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;  // 判断是否存在以给定前缀开始的单词
    }

    //用于搜索前缀。它从根节点开始，逐个字符遍历前缀，根据字符计算索引，
    // 如果子节点不存在，则说明前缀不存在，返回 null，
    // 否则将指针移动到下一个子节点，最后返回前缀的最后一个字符节点。
    private Trie searchPrefix(String prefix) {
        Trie node = this;  // 从根节点开始搜索前缀
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';  // 计算当前字符在子节点数组中的索引
            if (node.children[index] == null) {
                return null;  // 如果子节点不存在，说明前缀不存在，返回null
            }
            node = node.children[index];  // 移动到下一个子节点
        }
        return node;  // 返回前缀的最后一个字符节点
    }
}
